package 简单.贪心思想;

/**
 * 给定 N 个无限容量且初始均空的水缸，每个水缸配有一个水桶用来打水，
 * 第 i 个水缸配备的水桶容量记作 bucket[i]。小扣有以下两种操作：
 * 升级水桶：选择任意一个水桶，使其容量增加为 bucket[i]+1
 * 蓄水：将全部水桶接满水，倒入各自对应的水缸
 * 每个水缸对应最低蓄水量记作 vat[i]，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。
 * 注意：实际蓄水量 达到或超过 最低蓄水量，即完成蓄水要求。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/o8SXZn
 */
public class 蓄水_lcp33 {

    public static void main(String[] args) {

        System.out.println(new 蓄水_lcp33().storeWater(new int[]{9988, 5017, 5130, 2445, 9896, 9151, 3625, 7801, 608, 3283, 1386, 979, 5209, 4182, 8234, 9870, 8714, 6435, 3800, 956, 4006, 5620, 7474, 1205, 6993, 3320, 1201, 7593, 905, 3816, 4522, 4560, 8027, 8219, 6686, 3779, 2141, 1240, 6504, 6612, 6921, 7329, 8145, 5745, 7652, 4340, 7933, 6246, 5157, 9447, 107, 9665, 3653, 2978, 9832, 4945, 4312, 2199, 449, 8432, 3230, 8163, 800, 6547, 1110, 1194, 9384, 632, 3275, 1229, 7230, 8643, 7613, 8256, 5043, 1288, 3088, 8997, 4554, 4755, 7433, 8146, 9722, 3469, 8863, 5831, 7816, 5058, 4316, 7946, 8402, 975, 2450, 4958, 9811, 9336, 21, 9309, 8999, 56},
                new int[]{9991, 6973, 7192, 9876, 9910, 9549, 3700, 8814, 1308, 9981, 9234, 7292, 7732, 8458, 8441, 9939, 9621, 7285, 7452, 2718, 6589, 7555, 8788, 3202, 7832, 4781, 8798, 9299, 2112, 9963, 8755, 7240, 9217, 8587, 6782, 9703, 8954, 3759, 6907, 7218, 7333, 8020, 8323, 5750, 9510, 8571, 8664, 8510, 9363, 9741, 8643, 9825, 4227, 8530, 9961, 8511, 8949, 7486, 9086, 9690, 5316, 9581, 9314, 8817, 7234, 8998, 9485, 5394, 7365, 1501, 7984, 9802, 9778, 8314, 7482, 7117, 5117, 9609, 8732, 9728, 9330, 8800, 9775, 6210, 8966, 7700, 8802, 7607, 8950, 9730, 9855, 1231, 5228, 5329, 9982, 9532, 3230, 9951, 9034, 8299}));

    }

    /**
     * 贪心+数学
     * 升级水桶是只针对一个水桶，而蓄水是针对所有水桶！
     * 所以需要枚举蓄水的次数 k ，得出 vat[i]/k 向上取值为
     * 最少需要的水桶容量，vat[i]/k - bucket[i] 为需要
     * 第 i 个水桶需要升级的次数
     */
    public int storeWater(int[] bucket, int[] vat) {
        int ans = Integer.MAX_VALUE;
        int maxK = 0;
        for (int i : vat) {
            maxK = Math.max(maxK, i);
        }
        if (maxK == 0) return 0;

        for (int k = 1; k <= maxK; k++) {
            int curAns = 0;
            for (int i = 0; i < vat.length; i++) {
                // 注意，这里只累加每个桶需要升级的次数
                curAns += Math.max(0, (vat[i] + k - 1) / k - bucket[i]);
            }
            ans = Math.min(ans, curAns + k);
        }
        return ans;
    }


}
